/*
https://leetcode.cn/problems/er-cha-shu-ren-wu-diao-du/solution/dfs-si-lu-dai-ma-he-zheng-ming-by-leetcode-solutio/
 */
public class SolutionLCP10 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public double minimalExecTime(TreeNode root) {
        double[] ans=dfs(root);
        return ans[0]-ans[1];
    }

    private double[] dfs(TreeNode root) {
        if (root==null){
            return new double[]{0,0};
        }
        double[] l=dfs(root.left);
        double[] r=dfs(root.right);
        double a=l[0],b=l[1],c=r[0],d=r[1];
        if ((c-2*d<=a && a<=c) || (a-2*b<=c && c<=a)){
            return new double[]{a+c+root.val,(a+c)/2};
        }
        if (a-2*b>c){
            return new double[]{a+c+root.val,b+c};
        }else {
            return new double[]{a+c+root.val,a+d};
        }
    }

    public static void main(String[] args) {
        System.out.println(new SolutionLCP10().minimalExecTime(new TreeNode(47,new TreeNode(74),new TreeNode(31))));
    }
}
